package com.wc.alorithm_luogu.P5461;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author congge
 * @Date 2023/4/24 11:02
 * @description https://www.luogu.com.cn/problem/P5461
 * 赦免战俘
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int bound = (int) Math.pow(2, n);
        int[][] map = new int[bound][bound];
        for (int[] row : map) {
            Arrays.fill(row, 1);
        }
        Main main = new Main();

        main.pardon(map, 0, bound, 0, bound);

//        main.pardon(map);
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < bound; i++) {
            stringBuilder.append(map[i][0]);
            for (int j = 1; j < bound; j++) {
                stringBuilder.append(" ");
                stringBuilder.append(map[i][j]);
            }
            stringBuilder.append("\n");
        }
        System.out.println(stringBuilder);
    }

    /**
     * 数学的方式 全部填充0
     */
    public void pardon(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            map[i][map.length - 1] = 1;
        }

        for (int i = 1; i < map.length; i++) {
            for (int j = 0; j < map.length - 1; j++) {
                map[i][j] = (map[i - 1][j] + map[i - 1][j + 1]) % 2;
            }
        }
    }


    /**
     * 打印的问题 需要全部填充1
     */
    public void pardon(int[][] map, int up, int down, int left, int right) {
//        pardonX(map, up, down, left, right );
        if (down - up == 1) {
            return;
        }
        int midUD = up + (down - up) / 2;
        int midLR = left + (right - left) / 2;
        // 右下
        pardon(map, midUD, down, midLR, right);
        // 右上
        pardon(map, up, midUD, midLR, right);
        // 左下
        pardon(map, midUD, down, left, midLR);
        for (int i = up; i < midUD; i++) {
            for (int j = left; j < midLR; j++) {
                map[i][j] = 0;
            }
        }
    }
}
